#include<iostream>
using namespace std;
#include<vector>
#include<algorithm>


class Solution {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int s1 = fc(nums,0,nums.size()-1);
        int s2 = lc(nums,0,nums.size()-1);
        return s1 >= s2;
    }
    //先手
    int fc(const vector<int>& nums,int L,int R) {
        if(L == R) {
            return nums[L];
        }
        int socre1 = nums[L] + lc(nums,L+1,R);
        int score2 = nums[R] + lc(nums,L,R-1);
        return max(socre1,score2);
    }
    //后手
    int lc(const vector<int>& nums,int L,int R) {
        //后手纸牌已经被先手拿走了
        if(L == R) {
            return 0;
        }
        //后手被先手决定 对方会把情况最差的留给我 因为二者之和一定
        int socre1 = fc(nums,L+1,R);
        int score2 = fc(nums,L,R-1);
        return min(socre1,score2);
    }
};

class Solution2 {
public:
    bool PredictTheWinner(vector<int>& nums) {
        int fdp[25][25];
        int ldp[25][25];
        int N = nums.size();
        for(int i = 0; i < N; i++) {
            fdp[i][i] = nums[i];
            ldp[i][i] = 0;
        }
        //斜线数目
        for(int i = N-1; i >= 1; i--) {
            for(int block = 0; block < i; block++) {
                int block_x = block;
                int block_y = N-i+block;
                //更新先手
                int score1 = nums[block_x] + ldp[block_x+1][block_y];
                int score2 = nums[block_y] + ldp[block_x][block_y-1];
                fdp[block_x][block_y] = max(score1,score2);
                //后手
                score1 = fdp[block_x+1][block_y];
                score2 = fdp[block_x][block_y-1];
                ldp[block_x][block_y] = min(score1,score2);
            }
        }
        int s1 = fdp[0][N-1];
        int s2 = ldp[0][N-1];
        return s1 >= s2;
    }
};

int main() {

}